package com.lisp.algorithm.test.sort;

import java.util.Arrays;

public class KMerge {

	public static void main(String[] args) {
		int a[] = {1, 2, 2, 
				4, 5, 5, 
				5, 8, 8, 
				9, 11, 12,
				13};
		kmerge(a, 3);
	}
	
	private static void kmerge(int a[], int k) {
		NodeHeap heap = new NodeHeap(a, k);
		int ret[] = new int[a.length];
		for(int i=0; i<a.length; i++) {
			Node root = heap.nodes[0];
			ret[i] = root.get();
			root.proceed();
			heap.heapify(0);
		}
		System.out.println(Arrays.toString(ret));
	}
	
	static class NodeHeap {
		private Node[] nodes;
		
		public NodeHeap(int a[], int k) {
			nodes = new Node[k];
			for(int i=0; i<k; i++) {
				nodes[i] = new Node(a, k, i, 0);
			}
			
			buildHeap();
		}

		private void buildHeap() {
			for(int i=nodes.length/2-1; i>=0; i--) {
				heapify(i);
			}
		}
		
		private void heapify(int i) {
			int minIndex = i;
			
			int leftIndex = leftIndex(i);
			if(leftIndex < nodes.length
					&& nodes[leftIndex].get() < nodes[minIndex].get()) {
				minIndex = leftIndex;
			}
			
			int rightIndex = leftIndex+1;
			if(rightIndex < nodes.length
					&& nodes[rightIndex].get() < nodes[minIndex].get()) {
				minIndex = rightIndex;
			}
			
			if(minIndex != i) {
				swap(minIndex, i);
				heapify(minIndex);
			}
		}
		
		private int leftIndex(int i) {
			return i*2 + 1;
		}
		
		private void swap(int i, int j) {
			Node tmp = nodes[i];
			nodes[i] = nodes[j];
			nodes[j] = tmp;
		}
	}
	
	static class Node {
		private int a[];
		private int nodeIndex;
		private int k;
		private int innerIndex;
		
		public Node(int[] a, int k, int nodeIndex, int innerIndex) {
			super();
			this.a = a;
			this.k = k;
			this.nodeIndex = nodeIndex;
			this.innerIndex = innerIndex;
		}
		
		public int get() {
			int index = nodeIndex + innerIndex*k;
			if(index >= a.length) {
				return Integer.MAX_VALUE;
			} else {				
				return a[index];
			}
		}

		public void proceed() {
			this.innerIndex++;
		}
	}
}
